package com.sicheng.lc.lc笔试.阿里篇;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/25 23:26
 */
public class 严格递增子序列 {
    /**
     * T3：严格递增序列
     * 输入n（1~200000）以及数组，从数组中删除一个子数组，使得剩余部分是严格递增序列。问序列最长的时候需要删除的子数组长度。
     * 例：
     * 6
     * 1 3 1 2 3 5
     * 2（删除1,3即可）
     * <p>
     * 6
     * 1 2 3 3 4 5
     * 3（删除3即可）
     * <p>
     * 7
     * 4 5 2 3 4 1 2
     * 5（删除前面5个或者后面5个）
     * <p>
     * 作者：WASoul-WAker
     * 链接：https://leetcode-cn.com/circle/discuss/TNtrdC/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (n == 1) {
            System.out.println(0);
            return;
        }
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 找到最长递增的后缀子数组
        // 6
        // 1 2 3 3 4 5 ==== > 3,4,5
        int right = nums.length - 2;
        for (; right >= 0; right--) {
            if (nums[right] >= nums[right + 1])
                break;
        }
        // 全局递增,不需要删除
        if (right == -1) {
            System.out.println(0);
            return;
        }
        // right指向 后缀递增数组的起始位置
        right++;
        int max = n - right;
        // 找到前缀递增数组 与后缀合并
        for (int i = 0; i < n - 1; i++) {
            //满足递增 容纳入前缀子数组
            if (i == 0 || nums[i] > nums[i - 1]) {
                //当前后缀 无法全局递增时，后缀子数组不断剪掉当前首元素让其可以合并
                while (nums[right] <= nums[i]) {
                    right++;
                }
                max = Math.max(max, n + i - right + 1);
            } else
                break;
        }

        System.out.println(n - max);

    }
}
